UVa/11385 - Da Vinci Code/11385.cpp

   1 /*
   2   Problem: 11385 - Da Vinci Code
   3   Author: Andrés Mejía-Posada
   4
   5   Que gonorrea de problema.
   6
   7   Accepted.
   8  */
   9
  10 using namespace std;
  11 #include <algorithm>
  12 #include <iostream>
  13 #include <iterator>
  14 #include <sstream>
  15 #include <fstream>
  16 #include <cassert>
  17 #include <climits>
  18 #include <cstdlib>
  19 #include <cstring>
  20 #include <string>
  21 #include <cstdio>
  22 #include <vector>
  23 #include <cmath>
  24 #include <queue>
  25 #include <deque>
  26 #include <stack>
  27 #include <map>
  28 #include <set>
  29
  30 #define D(x) cout << #x " is " << x << endl
  31
  32 vector<int> fib;
  33
  34 int binary_search(int what, const vector<int> &where){
  35   int n = where.size();
  36   int low = 0, high = n - 1;
  37   while (low < high){
  38     int mid = (low + high) / 2;
  39     if (where[mid] < what){
  40       low = mid + 1;
  41     }else{
  42       high = mid;
  43     }
  44   }
  45   if (where[low] != what) return -1;
  46   return low;
  47 }
  48
  49 int main(){
  50   fib.push_back(1);
  51   fib.push_back(2);
  52   while (fib[fib.size()-1] + fib[fib.size()-2] > 0){ //Before overflow
  53     fib.push_back(fib[fib.size()-1] + fib[fib.size()-2]);
  54   }
  55
  56   int T;
  57   for(cin >> T; T--; ){
  58     int n;
  59     cin >> n;
  60     vector<int> nums(n);
  61     for (int i=0; i<n; ++i) cin >> nums[i];
  62
  63     string s;
  64     getline(cin, s);
  65     getline(cin, s);
  66     for (int i=0; i<s.size(); ++i)
  67       if (!isupper(s[i])){
  68         s.erase(i, 1);
  69         i--;
  70       }
  71
  72     vector<int> pos(n);
  73     for (int i=0; i<n; ++i){
  74       pos[i] = binary_search(nums[i], fib);
  75     }
  76
  77     string ans( *(max_element(pos.begin(), pos.end())) + 1, ' ');
  78
  79     for (int i=min(s.size(), pos.size()) - 1; i >= 0; --i){
  80       ans[pos[i]] = s[i];
  81     }
  82
  83     cout << ans << endl;
  84
  85   }
  86
  87   return 0;
  88 }